/*
    TSPFile - TSPLIB file parser
    Copyright (C) 2011  Laurent Poirrier

    This program is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program.  If not, see <http://www.gnu.org/licenses/>.
*/
#include <fstream>
#include <sstream>
#include <iostream>
#include <string>
#include <cmath>
#include "TSPClasses.hpp"
#include "TSPFile.hpp"

// **************************************************************************
// 
// **************************************************************************
TSPFile::TSPFile()
	: n(0)
{
}

TSPFile::TSPFile(const std::string &fileName)
	: n(0)
{
	load(fileName);
}

TSPFile::~TSPFile()
{
}

void TSPFile::clear()
{
	n = 0;
	name.clear();
	edge.clear();
	vertex.clear();
	forced.clear();
}

// **************************************************************************
// 
// **************************************************************************
static double TSPLongLat(double x)
{
	double degree, minute;
	
	degree = (int)x; // round towards zero
	minute = x - degree;
	return(3.141592 * (degree + 5.0 * minute / 3.0) / 180.0);
}

// ******************************************************************
#define EDGE_EXPLICIT	0
#define EDGE_EUCLIDIAN	1
#define EDGE_MAX	2
#define EDGE_MANHATTAN	3
#define EDGE_GEOGRAPHIC	4
#define EDGE_ATT	5
static double TSPDistance(int edgeFunc, int edgeDim, bool edgeCeil,
	TSPCoord &i, TSPCoord &j)
{
	double d = 0.0;
	
	if (edgeFunc == EDGE_EUCLIDIAN) {
		double dx = i.x - j.x;
		double dy = i.y - j.y;
		double dz = i.z - j.z;
		
		d = sqrt(dx * dx + dy * dy + dz * dz);
	} else if (edgeFunc == EDGE_ATT) {
		double dx = i.x - j.x;
		double dy = i.y - j.y;
		double dz = i.z - j.z;
		
		d = sqrt((dx * dx + dy * dy + dz * dz) / 10.0);
	} else if (edgeFunc == EDGE_MAX) {
		double dx = fabs(i.x - j.x);
		double dy = fabs(i.y - j.y);
		double dz = fabs(i.z - j.z);
		
		d = std::max(dx, std::max(dy, dz));
	} else if (edgeFunc == EDGE_MANHATTAN) {
		double dx = fabs(i.x - j.x);
		double dy = fabs(i.y - j.y);
		double dz = fabs(i.z - j.z);
		
		d = dx + dy + dz;
	} else if (edgeFunc == EDGE_GEOGRAPHIC) {
		double iLong, iLat, jLong, jLat;
		iLat  = TSPLongLat(i.x);
		iLong = TSPLongLat(i.y);
		jLat  = TSPLongLat(j.x);
		jLong = TSPLongLat(j.y);
		
		double q1 = cos(iLong - jLong);
		double q2 = cos(iLat - jLat);
		double q3 = cos(iLat + jLat);
		
		d = 6378.388 * acos(0.5 * ((1.0 + q1) * q2 - (1.0 - q1) * q3));
	}
	
	if (edgeCeil)
		d = ceil(d);
	else
		d = round(d);
	
	return(d);
}

// ******************************************************************
static int TSPReadCoord(std::ifstream &f, int &lnb,
	int n, std::vector<TSPCoord> &vertex, int cDim)
{
	vertex.resize(n);
	
	for (int i = 0; i < n; i++) {
		int j = 0;
		
		lnb++;
		f >> j;
		if (f.fail())
			return(-1);
		j--;
		if ((j < 0) || (j >= n))
			return(-1);

		f >> vertex[j].x;
		f >> vertex[j].y;
		if (cDim == 3)
			f >> vertex[j].z;
		else
			vertex[j].z = 0.0;

		if (f.fail())
			return(-1);
	}
	
	return(0);
}

static int TSPReadEdges(std::ifstream &f, int &lnb,
	int n, EdgeData<double> &edge,
	bool eeFull, bool eeRowWise, bool eeDiag, bool eeUpper)
{
	edge.resize(n);

	for (int l = 0; l < n; l++) {
		lnb++;
		for (int c = 0; c < n; c++) {
			int i = (eeRowWise) ? l : c;
			int j = (eeRowWise) ? c : l;
			
			if ((eeFull)
			||  (( eeDiag ) && (i == j))
			||  (( eeUpper) && (i < j))
			||  ((!eeUpper) && (i > j))) {
				double v;
				f >> v;
				
				if (i != j)
					edge(i, j) = v;
			}
		}

		if (f.fail())
			return(-1);
	}
	
	return(0);
}

static int TSPReadTour(std::ifstream &f, int &lnb,
	int &n, EdgeData<double> &edge)
{
	std::vector<int> tour;
	
	while(!f.eof()) {
		int j = 0;
		
		lnb++;
		f >> j;
		if ((f.fail()) && (!f.eof()))
			return(-1);
		
		if (j == -1)
			break;
		
		tour.push_back(j - 1);
	}
	
	if (n == 0)
		n = tour.size();
	
	if (n != (int)tour.size())
		return(-1);
	
	for (int i = 0; i < n; i++) {
		if ((tour[i] < 0) || (tour[i] >= n))
			return(-1);
	}
	
	edge.resize(n);
	edge.set(0.0);
	
	for (int i = 0; i < n; i++) {
		int j = (i + 1) % n;
		
		edge(tour[i], tour[j]) = 1.0;
	}
	
	return(0);
}

static int TSPReadFix(std::ifstream &f, int &lnb,
	int n, TSPFixing &forced)
{
	forced.clear();
	forced.resize(n);
	forced.unfix();
	
	while(true) {
		lnb++;
		
		int i, j;
		
		f >> i;
		if (f.fail())
			return(-1);
		if (i == -1)
			return(0);
		
		f >> j;
		if (f.fail())
			return(-1);
		
		i--;
		j--;
		if ((i < 0) || (i >= n) || (j < 0) || (j >= n))
			return(-1);
		
		forced.fix(i, j, true);
	}
}


// ******************************************************************
int TSPFile::load(const std::string &fileName, int maxN)
{
	clear();
	
	std::ifstream f(fileName.c_str());
	int lnb = 0;
	
	if (!f) {
		std::cerr << fileName << ": Failed to open file" << std::endl;
		return(-1);
	}
	
	int edgeFunc = EDGE_EXPLICIT;
	int edgeDim = 0;
	bool edgeCeil = false;
	bool eeFull = true, eeRowWise = true, eeDiag = true, eeUpper = false;
	int cDim = 0;
	
	while(!f.eof()) {
		std::string line;
		
		getline(f, line);
		lnb++;
		
		//std::cerr << fileName << ":" << lnb
		//	<< ": [" << line << "]" << std::endl;
		
		if ((f.fail()) && (!f.eof())) {
			std::cerr << fileName << ":" << lnb
				<< ": Read error" << std::endl;
			return(-1);
		}
		
		std::stringstream s(line);
		std::string tk, arg;
		
		s >> tk;
		
		if (tk.empty())
			continue;

		if (*(tk.end() - 1) == ':') {
			tk.erase(tk.end() - 1);
		} else {
			std::string colon;
			
			s >> colon;
			
			if ((s.good()) && (colon != ":")) {
				std::cerr << fileName << ":" << lnb
					<< ": Malformed spec (at "
					<< colon << ")" << std::endl;
				return(-1);
			}
		}
		
		//std::cerr << fileName << ":" << lnb
		//	<< ": {" << tk << "}" << std::endl;

		if (tk == "NAME") {
			s >> name;
			//std::cerr << fileName << ": " << arg << std::endl;
		} else if (tk == "TYPE") {
			s >> arg;
			if ((arg != "TSP") && (arg != "TOUR")) {
				std::cerr << fileName << ":" << lnb << ": "
					<< arg << ": Expected TSP or TOUR"
					<< std::endl;
				return(-1);
			}
		} else if (tk == "COMMENT") {
		} else if (tk == "DIMENSION") {
			s >> n;
			if (s.fail()) {
				std::cerr << fileName << ":" << lnb
					<< ": Malformed line" << std::endl;
				return(-1);
			}
		} else if (tk == "EDGE_WEIGHT_TYPE") {
			s >> arg;
			
			if (arg == "EXPLICIT") {
				edgeFunc = EDGE_EXPLICIT;
			} else if (arg == "EUC_2D") {
				edgeFunc = EDGE_EUCLIDIAN; edgeDim = 2;
			} else if (arg == "EUC_3D") {
				edgeFunc = EDGE_EUCLIDIAN; edgeDim = 3;
			} else if (arg == "MAX_2D") {
				edgeFunc = EDGE_MAX; edgeDim = 2;
			} else if (arg == "MAX_3D") {
				edgeFunc = EDGE_MAX; edgeDim = 3;
			} else if (arg == "MAN_2D") {
				edgeFunc = EDGE_MANHATTAN; edgeDim = 2;
			} else if (arg == "MAN_3D") {
				edgeFunc = EDGE_MANHATTAN; edgeDim = 3;
			} else if (arg == "CEIL_2D") {
				edgeFunc = EDGE_EUCLIDIAN; edgeDim = 2;
				edgeCeil = true;
			} else if (arg == "GEO") {
				edgeFunc = EDGE_GEOGRAPHIC; edgeDim = 2;
				edgeCeil = true;
			} else if (arg == "ATT") {
				edgeFunc = EDGE_ATT; edgeDim = 2;
				edgeCeil = true;
			} else {
				std::cerr << fileName << ":" << lnb << ": "
					<< arg << ": Unknown edge weight type"
					<< std::endl;
				return(-1);
			}
		} else if (tk == "EDGE_WEIGHT_FORMAT") {
			s >> arg;
			
			if (arg == "FUNCTION") {
			} else if (arg == "FULL_MATRIX") {
				edgeFunc = EDGE_EXPLICIT;
				eeFull = true;
			} else if (arg == "UPPER_ROW") {
				edgeFunc = EDGE_EXPLICIT;
				eeFull = false; eeRowWise = true;
				eeDiag = false; eeUpper = true;
			} else if (arg == "LOWER_ROW") {
				edgeFunc = EDGE_EXPLICIT;
				eeFull = false; eeRowWise = true;
				eeDiag = false; eeUpper = false;
			} else if (arg == "UPPER_DIAG_ROW") {
				edgeFunc = EDGE_EXPLICIT;
				eeFull = false; eeRowWise = true;
				eeDiag =  true; eeUpper = true;
			} else if (arg == "LOWER_DIAG_ROW") {
				edgeFunc = EDGE_EXPLICIT;
				eeFull = false; eeRowWise = true;
				eeDiag =  true; eeUpper = false;
			} else if (arg == "UPPER_COL") {
				edgeFunc = EDGE_EXPLICIT;
				eeFull = false; eeRowWise = false;
				eeDiag = false; eeUpper = true;
			} else if (arg == "LOWER_COL") {
				edgeFunc = EDGE_EXPLICIT;
				eeFull = false; eeRowWise = false;
				eeDiag = false; eeUpper = false;
			} else if (arg == "UPPER_DIAG_COL") {
				edgeFunc = EDGE_EXPLICIT;
				eeFull = false; eeRowWise = false;
				eeDiag =  true; eeUpper = true;
			} else if (arg == "LOWER_DIAG_COL") {
				edgeFunc = EDGE_EXPLICIT;
				eeFull = false; eeRowWise = false;
				eeDiag =  true; eeUpper = false;
			} else {
				std::cerr << fileName << ":" << lnb << ": "
					<< arg << ": Unknown edge weight format"
					<< std::endl;
				return(-1);
			}
		} else if (tk == "NODE_COORD_TYPE") {
			s >> arg;
			
			if (arg == "TWOD_COORDS") {
				cDim = 2;
			} else if (arg == "THREED_COORDS") {
				cDim = 3;
			} else if (arg == "NO_COORDS") {
				cDim = 0;
			} else {
				std::cerr << fileName << ":" << lnb << ": "
					<< arg << ": Unknown coordinates type"
					<< std::endl;
				return(-1);
			}
		} else if (tk == "DISPLAY_DATA_TYPE") {
			s >> arg;
			
			if (arg == "COORD_DISPLAY") {
			} else if (arg == "TWOD_DISPLAY") {
			} else if (arg == "NO_DISPLAY") {
			} else {
				std::cerr << fileName << ":" << lnb << ": "
					<< arg << ": Unknown display type"
					<< std::endl;
				return(-1);
			}
		} else if (tk == "NODE_COORD_SECTION") {
			if (!cDim)
				cDim = (edgeDim) ? edgeDim : 2;
			if (TSPReadCoord(f, lnb, n, vertex, cDim)) {
				std::cerr << fileName << ":~" << lnb
					<< ": Malformed NODE_COORD_SECTION"
					<< std::endl;
				return(-1);
			}
		} else if (tk == "EDGE_WEIGHT_SECTION") {
			if (TSPReadEdges(f, lnb, n, edge,
			eeFull, eeRowWise, eeDiag, eeUpper)) {
				std::cerr << fileName << ":~" << lnb
					<< ": Malformed EDGE_WEIGHT_SECTION"
					<< std::endl;
				return(-1);
			}
		} else if (tk == "DISPLAY_DATA_SECTION") {
			bool nok;
			
			if (vertex.size()) {
				std::vector<TSPCoord> tmp;
				
				nok = TSPReadCoord(f, lnb, n, tmp, 2);
			} else {
				nok = TSPReadCoord(f, lnb, n, vertex, 2);
			}
			
			if (nok) {
				std::cerr << fileName << ":~" << lnb
					<< ": Malformed DISPLAY_DATA_SECTION"
					<< std::endl;
				return(-1);
			}
		} else if (tk == "TOUR_SECTION") {
			if (TSPReadTour(f, lnb, n, edge)) {
				std::cerr << fileName << ":~" << lnb
					<< ": Malformed TOUR_SECTION"
					<< std::endl;
				return(-1);
			}
		} else if (tk == "FIXED_EDGES_SECTION") {
			if (TSPReadFix(f, lnb, n, forced)) {
				std::cerr << fileName << ":~" << lnb
					<< ": Malformed FIXED_EDGES_SECTION"
					<< std::endl;
				return(-1);
			}
		} else if (tk == "EOF") {
			break;
		} else {
			std::cerr << fileName << ":" << lnb << ": "
				<< tk << ": Unknown spec" << std::endl;
			return(-1);
		}
	}
	
	if ((edgeFunc) && (!edge.vertices())) {
		if ((int)vertex.size() != n) {
			std::cerr << fileName << ": expected NODE_COORD_SECTION"
				<< std::endl;
			return(-1);
		}
		
		if ((maxN > 0) && (n > maxN)) {
			std::cerr << fileName
				<< ": " << n << " vertices ("
				<< ((size_t)n * (n - 1) / 2)
				<< " edges), max = " << maxN << " vertices"
				<< std::endl;
			return(-1);
		}
		
		edge.resize(n);
		
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < i; j++) {
				edge(i, j) = TSPDistance(edgeFunc, edgeDim,
					edgeCeil,
					vertex[i], vertex[j]);
			}
		}
	}
	
	return(0);
}



